
#include "RBTree.h"
RBNode* Init(int value){
    RBNode* node = (RBNode*) malloc(sizeof(RBNode));
    memset(node,0,sizeof(RBNode));
    node->value=value;
    node->isRed = 1;
    return node;
}
//右旋转
void RightRotate2(RBNode* node, RBNode ** root){
    int isNodeLeft = node->isLeft;
    RBNode * grand = node->parent;
    RBNode * child = node->left;
    RBNode * tmp = child->right;

    node->left = tmp;
    if(tmp){
        tmp->parent = node;
        tmp->isLeft = 1;
    }

    child->right = node;
    node->parent = child;
    node->isLeft = 0;

    child->parent = grand;
    if(grand == NULL){
        *root = child;
        return;
    }else if(isNodeLeft){
        grand->left = child;
        child->isLeft = 1;
    } else {
        grand->right = child;
        child->isLeft = 0;
    }
}
void RightRotate(RBNode* parent , RBNode * newNode, RBNode ** root){
    RBNode * grand = parent->parent;
    int isPLeft = parent->isLeft;
    //多余节点
    RBNode * tmp = newNode->right;
    parent->left = tmp;
    if(tmp){
        tmp->parent = parent;
        tmp->isLeft = 1;
    }
    //parent,n关系
    newNode->right = parent;
    parent->parent = newNode;
    parent->isLeft = 0;
    //g关系
    newNode->parent = grand;
    if(grand == NULL) {
        //替换根节点
        *root = newNode;
        return;
    } else if(isPLeft) {
        grand->left = newNode;
        newNode->isLeft = 1;
    } else {
        grand->right = newNode;
        newNode->isLeft = 0;
    }
}
//左旋转
void LeftRotate2(RBNode* node, RBNode ** root){
    int isNodeLeft = node->isLeft;
    RBNode * grand = node->parent;
    RBNode * child = node->right;
    RBNode * tmp = child->left;

    node->right = tmp;
    if(tmp){
        tmp->parent = node;
        tmp->isLeft = 0;
    }

    child->left = node;
    node->parent = child;
    node->isLeft = 1;

    child->parent = grand;
    if(grand == NULL){
        *root = child;
        return;
    }else if(isNodeLeft){
        grand->left = child;
        child->isLeft = 1;
    } else {
        grand->right = child;
        child->isLeft = 0;
    }
}
void LeftRotate(RBNode* parent, RBNode * newNode, RBNode ** root){
    RBNode * grand = parent->parent;
    int isPLeft = parent->isLeft;
    //多余节点
    RBNode* tmp = newNode->left;
    parent->right = tmp;
    if(tmp){
        tmp->parent = parent;
        tmp->isLeft = 0;
    }
    //parent,newNode关系
    newNode->left = parent;
    parent->parent = newNode;
    parent->isLeft = 1;

    //grand关系
    newNode->parent = grand;
    if(grand == NULL){
        //替换根节点
        *root = newNode;
        return;
    }
    if(isPLeft){
        grand->left = newNode;
        newNode->isLeft = 1;
    } else {
        grand->right = newNode;
        newNode->isLeft = 0;
    }

}
void FixAfterInsert(RBNode* parent, RBNode* newNode, RBNode** root){
    if(parent == NULL){
        *root = newNode;
        return;
    }
    //双红
    if(parent->isRed && newNode->isRed){
        RBNode* grand = parent->parent;
        RBNode * uncle = parent->isLeft ? grand->right : grand->left;
        //U存在且为红色
        if(uncle && uncle->isRed){
            //GPU反色
            grand->isRed = 1;
            parent->isRed = 0;
            uncle->isRed = 0;
            //判断grand是不是根节点
            if(grand == *root){
                grand->isRed = 0;
            } else {
                FixAfterInsert(grand->parent,grand,root);
            }

        }
        //U为黑色
        else if(uncle == 0 || uncle->isRed == 0){
            //左左型
            if(parent->isLeft && newNode->isLeft){
                grand->isRed = 1;
                parent->isRed = 0;
                RightRotate(grand,parent,root);
            } else if(parent->isLeft && newNode->isLeft == 0) { //左右型号
                LeftRotate(parent,newNode,root);
                grand->isRed = 1;
                newNode->isRed = 0;
                RightRotate(grand,newNode,root);
            } else if(parent->isLeft == 0 && newNode->isLeft == 0){//右右型
                grand->isRed = 1;
                parent->isRed = 0;
                LeftRotate(grand,parent,root);
            } else{ //右左型
                RightRotate(parent, newNode, root);
                grand->isRed = 1;
                newNode->isRed = 0;
                LeftRotate(grand, newNode, root);
            }
        }
    }
}
//插入
RBNode* RBInsert(RBNode ** root, int value){
    RBNode * newNode = Init(value);
    if(root != NULL){
        RBNode* cur  = *root;
        RBNode* parent = NULL;

        while(cur){
            if(value == cur->value) {
                return NULL;
            } else if(value > cur->value){
                parent = cur;
                cur = cur->right;
                newNode->isLeft = 0;
            } else if(value < cur->value){
                parent = cur;
                cur = cur->left;
                newNode->isLeft = 1;
            }
        }
        newNode->parent = parent;
        if(newNode->isLeft)
            parent->left = newNode;
        else
            parent->right = newNode;
        FixAfterInsert(parent,newNode, root);
    } else {
        newNode->isRed = 0;
        return newNode;
    }
}
RBNode* FindMin(RBNode* root) {
    assert(root);
    if (root->left == NULL) {
        return root;
    }
    return FindMin(root->left);
}
RBNode* FindMax(RBNode* root) {
    assert(root);
    if (root->right == NULL) {
        return root;
    }
    return FindMax(root->right);
}
void SuccessorRemove(RBNode ** root, RBNode * successor){
    RBNode * sParent = successor->parent;
    //兄弟节点
    RBNode * sBrother = successor->isLeft ?
                        sParent->right : sParent->left;
    //兄弟的子节点
    RBNode * sBL = sBrother ?
                   sBrother->left : NULL;
    RBNode * sBR = sBrother ?
                   sBrother->right : NULL;
    // 1.替换节点为红
    if(successor->isRed)
        return;//什么都不做
    //没有兄弟节点
    if(sBrother == NULL)
        return;//什么都不做
    //替换节点颜色情况
    if(successor->isLeft){
        //2.替换节点为黑
        //2.1替换节点为左型
        //2.1.1兄弟节点是红
        if(sBrother->isRed){
            sBrother->isRed = 0;
            sParent->isRed = 1;
            LeftRotate(sParent,sBrother,root);
        }
        //2.1.2兄弟节点是黑色，父节点子节点颜色无法确定
        else {
            //2.1.2.1：替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色
            if(sBR&&sBR->isRed){
                sBrother->isRed = sParent->isRed;
                sBR->isRed = 0;
                sParent->isRed = 0;
                LeftRotate(sParent, sBrother, root);
            }
            //2.1.2.2：替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点
            else if(sBR&&sBL&&sBR->isRed == 0 && sBL->isRed){
                sBrother->isRed = 1;
                sBL->isRed = 0;
                RightRotate(sBrother,sBL,root);
                sBL->isRed = sParent->isRed;
                sParent->isRed = 0;
                sBrother->isRed = 0;
                LeftRotate(sParent, sBL, root);
            }
            //2.1.2.3子节点都为黑色
            else if((sBR == NULL&&sBL ==NULL)||(sBR->isRed == 0 && sBL->isRed == 0)) {
                if(sParent->parent == NULL){
                    sBrother->isRed = 1;
                } else {
                    //新的节点为 红+黑
                    if(sParent->parent->left->isRed == 0){
                        sBrother->isRed = 1;
                        //直接把这个节点设置为黑色
                        sParent->isRed = 0;
                    } else{
                        //黑+黑
                        LeftRotate2(sParent,root);
//                    SuccessorRemove(root, sParent);
                    }
                }

            }
        }
    } else {
        //2.1.2.1替换结点的兄弟结点是红结点
        if(sBrother->isRed){
            sBrother->isRed = 0;
            sParent->isRed = 1;
            RightRotate(sParent,sBrother,root);
        }
        //2.2.2：替换结点的兄弟结点是黑结点
        else {
            //2.2.2.1：替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色
            if(sBL&&sBL->isRed == 1){
                sBrother->isRed = sParent->isRed;
                sParent->isRed = 0;
                sBL->isRed = 0;
                RightRotate(sParent,sBrother,root);
            }
            //2.2.2.2：替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点
            else if(sBL&&sBR&&sBL->isRed == 0 && sBR->isRed){
                sBrother->isRed = 1;
                sBR->isRed = 0;
                LeftRotate(sBrother,sBR,root);
                sBR->isRed = sParent->isRed;
                sParent->isRed = 0;
                sBrother->isRed = 0;
                RightRotate(sParent, sBR, root);
            }
            //2.1.2.3：替换结点的兄弟结点的子结点都为黑结点
            else if((sBR == NULL&&sBL ==NULL)||(sBR->isRed == 0 && sBL->isRed == 0)) {
                if(sParent->parent == NULL) {
                    sBrother->isRed = 1;
                } else{
                    //新的节点为 红+黑
                    if(sParent->parent->right->isRed == 0){
                        //直接把这个节点设置为黑色
                        sBrother->isRed = 1;
                        sParent->isRed = 0;
                    } else {
                        //黑+黑
                        RightRotate2(sParent,root);
//                    SuccessorRemove(root, sParent);
                    }
                }
            }
        }

    }
}
//移除
void RBRemove(RBNode** root, int value){
    RBNode * cur = *root;

    while(cur) {
        if(value > cur->value){
            cur = cur->right;
        } else if(value < cur->value){
            cur = cur->left;
        } else {
            break;
        }
    }

    if(cur == NULL)//没找到
        return;

    RBNode* parent = cur->parent;
    RBNode* left = cur->left;
    RBNode* right = cur->right;
    if(left == NULL && right == NULL) { //叶子节点
        if(cur != *root){   //删除的节点不为根节点
            if(cur ->isLeft)
                parent->left = NULL;
            else
                parent->right = NULL;
        }
        free(cur);
    } else if(left && right){  //两个子节点
        RBNode * successor = FindMin(right);    //替换节点
        SuccessorRemove(root,successor);

        RBNode * successorChild = successor->right;
        RBNode * sParent = successor->parent;
        if(successorChild){ //有右子节点（不会有左子节点的情况）
            if(successor->isLeft){
                sParent->left = successorChild;
                successorChild->isLeft = 1;

            }
            else{
                sParent->right = successorChild;
                successorChild->isLeft = 0;
            }
            successorChild->parent = sParent;
            FixAfterInsert(sParent,successorChild,root);
        } else {//没有子节点
            if(successor->isLeft)
                sParent->left = NULL;
            else
                sParent->right = NULL;
        }
        cur->value = successor->value;
        free(successor);
    } else {    //一个子节点
        RBNode * child = NULL;
        if(left)
            child = left;
        else
            child = right;

        if(cur != *root) {
            if(cur->isLeft){
                parent->left = child;
                child->isLeft = 1;
            } else {
                parent->right = child;
                child->isLeft = 0;
            }
            child->isRed = 0;
            free(cur);
        } else {    //cur是根节点
//            cur->value = child->value;
//            //这个child节点一定没有子节点
//            if(child->isLeft)
//                cur->left = NULL;
//            else
//                cur->right = NULL;
//            free(child);
            free(cur);
            child->isRed = 0;
            *root = child;
        }
    }

}
int FindHeight(RBNode* root) {
    if (root == NULL)
        return -1;
    int right = FindHeight(root->right);
    int left = FindHeight(root->left);

    return fmaxl(right, left) + 1;
}
void RBPrint(RBNode * root){
    if(root == NULL) return;

    int height = FindHeight(root);

    RBNode *** nodes = (RBNode***) malloc(sizeof(RBNode**) * (height + 1));

    for(int i = 0; i <= height; i++){
        int sz = (int)(pow(2,i));
        RBNode ** level = (RBNode**) malloc(sizeof(RBNode*) * sz);

        if(i == 0){
            level[0] = root;
        } else {
            RBNode ** lastLevel = nodes[i-1];
            int t = 0;
            for(int j = 0; j < sz / 2; j++){
                if(lastLevel[j] == NULL){
                    level[t++] = NULL;
                    level[t++] = NULL;
                } else {
                    level[t++] = lastLevel[j]->left;
                    level[t++] = lastLevel[j]->right;
                }
            }
        }

        nodes[i] = level;
        for(int t = 0; t < sz; t++){
            for(int j = 0; j < pow(2, height - i) * 2; j++){
                printf(" ");
            }
            if(level[t] == NULL){
                printf("**");
            } else {
                if(level[t]->isRed){
                    printf(RED"%2d"NONE, level[t]->value);
                } else {
                    printf("%2d",level[t]->value);
                }
            }
            if(i < height){
                int max = 2;
                int x = i + 1;
                while(x < height){
                    max += pow(2, height - x) * 2;
                    x++;
                }
                for(int j = 0; j < max; j++){
                    printf(" ");
                }
            }
        }
        printf("\n");
    }
    for(int i = 0; i < pow(2, height); i++){
        printf("----");
    }
    printf("\n");
    //释放
    for(int i =0; i <= height; i++){
        free(nodes[i]);
    }
    free(nodes);
}
void RBWrite(RBNode* root){
    if(root == NULL) return;

    int height = FindHeight(root);

    RBNode *** nodes = (RBNode***) malloc(sizeof(RBNode**) * (height + 1));

    FILE *pf = fopen("test.txt","a+");

    for(int i = 0; i <= height; i++){
        int sz = (int)(pow(2,i));
        RBNode ** level = (RBNode**) malloc(sizeof(RBNode*) * sz);

        if(i == 0){
            level[0] = root;
        } else {
            RBNode ** lastLevel = nodes[i-1];
            int t = 0;
            for(int j = 0; j < sz / 2; j++){
                if(lastLevel[j] == NULL){
                    level[t++] = NULL;
                    level[t++] = NULL;
                } else {
                    level[t++] = lastLevel[j]->left;
                    level[t++] = lastLevel[j]->right;
                }
            }
        }

        nodes[i] = level;
        for(int t = 0; t < sz; t++){
            for(int j = 0; j < pow(2, height - i) * 4; j++){
                fprintf(pf," ");
            }
            if(level[t] == NULL){
                fprintf(pf,"**  ");
            } else {
                if(level[t]->isRed){
                    fprintf(pf," %2d ",level[t]->value );
                } else {
                    fprintf(pf,"_%2d_",level[t]->value);
                }
            }
            if(i < height){
                int max = 2;
                int x = i + 1;
                while(x < height){
                    max += pow(2, height - x) * 2;
                    x++;
                }
                for(int j = 0; j < max; j++){
                    fprintf(pf,"  ");
                }
            }
        }
        fprintf(pf,"\n");
    }
    for(int i = 0; i < pow(2, height); i++){
        fprintf(pf,"--------");
    }
    fprintf(pf,"\n");
    //释放
    for(int i =0; i <= height; i++){
        free(nodes[i]);
    }
    free(nodes);
    fclose(pf);
}
void RBClear(){
    FILE *pf = fopen("test.txt","w");
    fclose(pf);
}